package com.javabasic.algorithm.leetcode;

/**
 * @Author xiongmin
 * @Description //TODO
 * @Date 2020/1/12 19:22
 * @Version 1.0
 * @link: https://leetcode-cn.com/problems/regions-cut-by-slashes/solution/
 **/
public class RegionsCutBySlashes {

    int[] f;

    /**
     * @解法：并查集解法
     * @param grid
     * @return
     */
    public int regionsBySlashes(String[] grid) {
        int row = grid.length;
        int col = grid[0].length();
        int arrLen = row * col * 4 + 1;
        f = new int[arrLen];
        // 将每一个方格有对角线分成4块，从上方顺时针标记1-4
        for (int i = 0; i < arrLen; i++) {
            f[i] = i;
        }

        System.out.println(row + " " + col);


        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (i+1 < row) {
                    // 当前方格的第3块和其下方方格的第一块
                    union(i*4*col+j*4+3,(i+1)*4*col+j*4+1);
                }
                if (j + 1 < col) {
                    // 当前方格的第2块和其右方方格的第4块
                    union(i*4*col+j*4+2,i*4*col+(j+1)*4+4);
                }
            }
        }

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i].charAt(j) == '/') {
                    // 当前方格的第1块和第4块
                    union(i*4*col+j*4+1,i*4*col+j*4+4);
                    // 当前方格的第2块和第3块
                    union(i*4*col+j*4+2,i*4*col+j*4+3);
                } else if (grid[i].charAt(j) == '\\') {
                    // 当前方格的第1块和第2块
                    union(i*4*col+j*4+1,i*4*col+j*4+2);
                    // 当前方格的第3块和第4块
                    union(i*4*col+j*4+4,i*4*col+j*4+3);
                } else {
                    // 将该方格的四块，全部合在一起
                    System.out.println(i + " " + j);
                    // 当前方格的第1块和第4块
                    union(i*4*col+j*4+1,i*4*col+j*4+4);
                    // 当前方格的第2块和第3块
                    union(i*4*col+j*4+2,i*4*col+j*4+3);
                    // 当前方格的第1块和第2块
                    union(i*4*col+j*4+1,i*4*col+j*4+2);
                }
            }
        }
        for (int i = 1; i < arrLen; i++) {
            System.out.println(findFather(i));
        }

        int result = 0;
        for (int i = 1; i < arrLen; i++) {
            if (f[i] == i) {
                result++;
            }
        }
        return result;
    }

    private int findFather(int x) {
        if (x == f[x]) return x;
        f[x] = findFather(f[x]);
        return f[x];
    }


    private void union(int x, int y) {
        int fx = findFather(x), fy = findFather(y);
        if (fx != fy) {
            f[fx] = fy;
        }
    }
}
